package com.test.daily.leetcode.y2022.m07.day0718.v04;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Tom on 2022/7/18
 */
public class Solution {
    public static class Node{
        int value;
        public Node left;
        public Node right;
        public Node(int value){
            this.value = value;
        }
    }
    public boolean isCBT(Node root){
        boolean leaf = false;
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            Node node = queue.poll();
            Node l = node.left;
            Node r = node.right;
            if((leaf && (l != null || r != null)) ||( l== null || r == null) ){
                return false;
            }
            if(l != null){
                queue.add(l);
            }
            if(r!= null){
                queue.add(r);
            }
            if(l == null || r == null){
                leaf = true;
            }
        }
        return true;
    }
    public static class Info{
        boolean isCBT;
        boolean isFull;
        int h;
        public Info(boolean isCBT, boolean isFull, int h){
            this.h = h;
            this.isCBT = isCBT;
            this.isFull = isFull;
        }
    }
    public boolean isCBT1(Node head){
        return process(head).isCBT;
    }
    public Info process(Node head){
        if(head == null){
            return new Info(true,true, 0);
        }
        Info leftInfo = process(head.left);
        Info rightInfo = process(head.right);
        int h = Math.max(leftInfo.h, rightInfo.h) + 1;
        boolean isCBT = false;
        boolean isFull = leftInfo.isFull && rightInfo.isFull && rightInfo.h == leftInfo.h;
        if(isFull){
            isCBT = true;
        } else {
            if(leftInfo.isCBT && rightInfo.isCBT){
                if(leftInfo.isFull && rightInfo.isFull && (leftInfo.h == rightInfo.h + 1)){
                    isCBT = true;
                }
                if(leftInfo.isCBT && rightInfo.isFull && (leftInfo.h == rightInfo.h + 1)){
                    isCBT = true;
                }
                if(leftInfo.isFull && rightInfo.isCBT && leftInfo.h == rightInfo.h){
                    isCBT = true;
                }
            }
        }
        return new Info(isCBT, isFull, h);
    }
}
